home *** CD-ROM | disk | FTP | other *** search
/ Reverse Code Engineering RCE CD +sandman 2000 / ReverseCodeEngineeringRceCdsandman2000.iso / RCE / Library / Manuels & Misc / Assembly / AOA.ZIP / CH05 / PROJ5_2.ASM < prev    next >
Encoding:
Assembly Source File  |  1996-02-03  |  25.1 KB  |  1,093 lines

  1. ; Project #2, Chapter five
  2. ;
  3. ; AMAZE.ASM
  4. ;
  5. ; A maze generation/solution program.
  6. ;
  7. ; This program generates an 80x25 maze and directly draws the maze on the
  8. ; video display.
  9. ;
  10. ; You need to supply some code to access the 80x25 cells of the maze on the
  11. ; video display.  For full details on how this program works, see the chapter
  12. ; on processes in the textbook.  Warning! This program is relatively complex.
  13. ; Don't try to understand how it works if you're working on this after
  14. ; just reading chapter five
  15. ;
  16. ; When this program runs it will generate a maze and then pause until you
  17. ; print a key.  Then it will solve the maze and stop on the next keypress.
  18. ;
  19. ; This version will only work on a color display.
  20.  
  21.  
  22.  
  23.  
  24. cseg        segment    para public 'code'
  25.         assume    cs:cseg, ds:dseg
  26.  
  27.  
  28. ; MazeAdrs computes the index into the maze array.
  29. ; Maze is a 27x82 array of words (maze:array[0..26,0..81] of word).
  30. ; The following procedure needs to compute the index into this array
  31. ; and return that index in the AX register.  On input, dx contains
  32. ; the X coordinate (0..81) and cx contains the Y coordinate (0..26).
  33. ; Each element of the array is a word.
  34. ;
  35.  
  36. MazeAdrs    textequ    <call DoMazeAdrs>
  37.  
  38. DoMazeAdrs    proc
  39.         push    bx
  40.         push    cx
  41.         push    dx
  42.  
  43.         mov    cl, dh
  44.         mov    dh, 0
  45.         mov    ch, 0
  46.         xchg    cx, dx
  47.  
  48. ; Do your computations here:
  49.     
  50.  
  51.  
  52. ; Complete your computations by this point.
  53.  
  54.         pop    dx
  55.         pop    cx
  56.         pop    bx
  57.         ret
  58. DoMazeAdrs    endp
  59.  
  60.  
  61. ; The following procedure needs to be just like the code above
  62. ; except the matrix it computes the index for is a 25x80 matrix,
  63. ; not a 27x82 matrix.  Once again, the X coordinate (0..79) is in
  64. ; CX and the Y coordinate (0..24) is in DX.  Use row major ordering.
  65. ; You may use the AX, BX, CX, and DX registers.  Return the index
  66. ; in the AX register.
  67.  
  68. ScrnAdrs    textequ    <call DoScrnAdrs>
  69.  
  70. DoScrnAdrs    proc
  71.         push    bx
  72.         push    cx
  73.         push    dx
  74.  
  75.         mov    cl, dh
  76.         mov    ch, 0
  77.         mov    dh, 0
  78.         dec    dx
  79.         dec    cx
  80.         xchg    cx, dx
  81.  
  82.  
  83. ; Do your computations here.
  84.  
  85.  
  86. ; Complete your computations by this point.
  87.  
  88.         pop    dx
  89.         pop    cx
  90.         pop    bx
  91.         ret
  92. DoScrnAdrs    endp
  93.  
  94.  
  95.  
  96. cseg        ends
  97.  
  98.  
  99.  
  100.  
  101. ; ***** Don't mess with anything beyond this point !!! ********
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.         .xlist
  109.         include     stdlib.a
  110.         includelib    stdlib.lib
  111.         .list
  112.  
  113. byp        textequ    <byte ptr>
  114.  
  115. dseg        segment    para public 'data'
  116.  
  117. ; Constants:
  118. ;
  119. ; Define the "ToScreen" symbol (to any value) if the maze is 80x25 and you
  120. ; want to display it on the video screen.
  121.  
  122. ToScreen    equ    0
  123.  
  124.  
  125. ; Maximum X and Y coordinates for the maze (matching the display).
  126.  
  127. MaxXCoord    equ    80
  128. MaxYCoord    equ    25
  129.  
  130. ; Useful X,Y constants:
  131.  
  132. WordsPerRow    =    MaxXCoord+2
  133. BytesPerRow    =    WordsPerRow*2
  134.  
  135. StartX        equ    1        ;Starting X coordinate for maze
  136. StartY        equ    3        ;Starting Y coordinate for maze
  137. EndX        equ    MaxXCoord    ;Ending X coordinate for maze
  138. EndY        equ    MaxYCoord-1    ;Ending Y coordinate for maze
  139.  
  140. EndLoc        =    ( (EndY-1)*MaxXCoord + EndX-1)*2
  141. StartLoc    =    ( (StartY-1)*MaxXCoord + StartX-1)*2
  142.  
  143. ; Special 16-bit PC character codes for the screen for symbols drawn during
  144. ; maze generation.  See the chapter on the video display for details.
  145.  
  146.         ifdef    mono        ;Mono display adapter.
  147.  
  148. WallChar    equ    7dbh        ;Solid block character
  149. NoWallChar    equ    720h        ;space
  150. VisitChar    equ    72eh        ;Period
  151. PathChar    equ    72ah        ;Asterisk
  152.  
  153.         else            ;Color display adapter.
  154.  
  155. WallChar    equ    1dbh        ;Solid block character
  156. NoWallChar    equ    0edbh        ;space
  157. VisitChar    equ    0bdbh        ;Period
  158. PathChar    equ    4e2ah        ;Asterisk
  159.  
  160.         endif
  161.  
  162.  
  163.  
  164.  
  165. ; The following are the constants that may appear in the Maze array:
  166.  
  167. Wall        =    0
  168. NoWall        =    1
  169. Visited        =    2
  170.  
  171. ; The following are the directions the demons can go in the maze
  172.  
  173. North        =    0
  174. South        =    1
  175. East        =    2
  176. West        =    3
  177.  
  178.  
  179. ; Some important variables:
  180.  
  181.  
  182. ; The Maze array must contain an extra row and column around the
  183. ; outside edges for our algorithm to work properly.
  184.  
  185. Maze        word    (MaxYCoord+2) dup ((MaxXCoord+2) dup (Wall))
  186.  
  187.  
  188.  
  189. ; PCB for the main program.  The last live demon will call this guy when
  190. ; it dies.
  191.  
  192. MainPCB        pcb    {}
  193.  
  194.  
  195. ; List of up to 32 demons.
  196.  
  197. MaxDemons    =    32            ;Must be a power of two.
  198. ModDemons    =    MaxDemons-1        ;Mask for MOD computation.
  199.  
  200. DemonList    pcb    MaxDemons dup ({})
  201.  
  202. DemonIndex    byte    0            ;Index into demon list.
  203. DemonCnt    byte    0            ;Number of demons in list.
  204.  
  205.  
  206. ; Random number generator seed (we'll use our random number generator
  207. ; rather than the standard library's because we want to be able to specify
  208. ; an initial seed value).
  209.  
  210. Seed        word    0
  211.  
  212. dseg        ends
  213.  
  214.  
  215.  
  216. ; The following is the segment address of the video display, change this
  217. ; from 0B800h to 0B000h if you have a monochrome display rather than a
  218. ; color display.
  219.  
  220. ScreenSeg    segment    at 0b800h
  221. Screen        equ    this word    ;Don't generate in date here!
  222. ScreenSeg    ends
  223.  
  224.  
  225. cseg        segment    para public 'code'
  226.         assume    cs:cseg, ds:dseg
  227.  
  228. ; Totally bogus random number generator, but we don't need a really
  229. ; great one for this program.  This code uses its own random number
  230. ; generator rather than the one in the Standard Library so we can
  231. ; allow the user to use a fixed seed to produce the same maze (with
  232. ; the same seed) or different mazes (by choosing different seeds).
  233.  
  234. RandNum        proc    near
  235.         push    cx
  236.         mov    cl, byte ptr Seed
  237.         and    cl, 7
  238.         add    cl, 4
  239.         mov    ax, Seed
  240.         xor    ax, 55aah
  241.         rol    ax, cl
  242.         xor    ax, Seed
  243.         inc    ax
  244.         mov    Seed, ax
  245.         pop    cx
  246.         ret
  247. RandNum        endp
  248.  
  249. ; Init-    Handles all the initialization chores for the main program.
  250. ;    In particular, it initializes the coroutine package, gets a
  251. ;    random number seed from the user, and initializes the video display.
  252.  
  253. Init        proc    near
  254.         print
  255.         byte    "Enter a small integer for a random number seed:",0
  256.         getsm
  257.         atoi
  258.         free
  259.         mov    Seed, ax
  260.  
  261. ; Fill the interior of the maze with wall characters, fill the outside
  262. ; two rows and columns with nowall values.  This will prevent the demons
  263. ; from wandering outside the maze.
  264.  
  265.  
  266. ; Fill the first row with Visited values.
  267.  
  268.         cld
  269.         mov    cx, WordsPerRow
  270.         lesi    Maze
  271.         mov    ax, Visited
  272.     rep    stosw
  273.  
  274. ; Fill the last row with NoWall values.
  275.  
  276.         mov    cx, WordsPerRow
  277.         lea    di, Maze+(MaxYCoord+1)*BytesPerRow
  278.     rep    stosw
  279.  
  280. ; Write a NoWall value to the starting position:
  281.  
  282.         mov    Maze+(StartY*WordsPerRow+StartX)*2, NoWall
  283.  
  284.  
  285. ; Write NoWall values along the two vertical edges of the maze.
  286.  
  287.         lesi    Maze
  288.         mov    cx, MaxYCoord+1
  289. EdgesLoop:    mov    es:[di], ax            ;Plug the left edge.
  290.         mov    es:[di+BytesPerRow-2], ax    ;Plug the right edge.
  291.         add    di, BytesPerRow
  292.         loop    EdgesLoop
  293.  
  294.  
  295.         ifdef    ToScreen
  296.  
  297. ; Okay, fill the screen with WallChar values:
  298.  
  299.         lesi    Screen
  300.         mov    ax, WallChar
  301.         mov    cx, 2000
  302.     rep    stosw
  303.  
  304. ; Write appropriate characters to the starting and ending locations:
  305.  
  306.         mov    word ptr es:Screen+EndLoc, PathChar
  307.         mov    word ptr es:Screen+StartLoc, NoWallChar
  308.  
  309.         endif    ;ToScreen
  310.  
  311.  
  312. ; Zero out the DemonList:
  313.  
  314.         mov    cx, (size pcb)*MaxDemons
  315.         lea    di, DemonList
  316.         mov    ax, dseg
  317.         mov    es, ax
  318.         xor    ax, ax
  319.     rep    stosb
  320.  
  321.         ret
  322. Init        endp
  323.  
  324.  
  325.  
  326. ; CanStart- This function checks around the current position
  327. ; to see if the maze generator can start digging a new tunnel
  328. ; in a direction perpendicular to the current tunnel.  You can
  329. ; only start a new tunnel if there are wall characters for at
  330. ; least two positions in the desired direction:
  331. ;
  332. ;            ##
  333. ;               *##
  334. ;            ##
  335. ;
  336. ; If "*" is current position and "#" represent wall characters
  337. ; and the current direction is north or south, then it is okay
  338. ; for the maze generator to start a new path in the east dir-
  339. ; ection.  Assuming "." represents a tunnel, you cannot start
  340. ; a new tunnel in the east direction if any of the following
  341. ; patterns occur:
  342. ;
  343. ;        .#    #.    ##    ##    ##    ##
  344. ;           *##     *##     *.#     *#.     *##     *##
  345. ;        ##    ##    ##    ##    .#    #.
  346. ;
  347. ; CanStart returns true (carry set) if we can start a new tunnel off the
  348. ; path being dug by the current demon.
  349. ;
  350. ; On entry,     dl is demon's X-Coordinate
  351. ;               dh is demon's Y-Coordinate
  352. ;        cl is demon's direction
  353.  
  354. CanStart    proc    near
  355.         push    ax
  356.         push    bx
  357.  
  358.         MazeAdrs        ;Compute index to demon(x,y) in maze.
  359.         mov    bx, ax
  360.  
  361. ; CL contains the current direction, 0=north, 1=south, 2=east, 3=west.
  362. ; Note that we can test bit #1 for north/south (0) or east/west (1).
  363.  
  364.         test    cl, 10b        ;See if north/south or east/west
  365.         jz    NorthSouth
  366.  
  367. ; If the demon is going in an east or west direction, we can start a new
  368. ; tunnel if there are six wall blocks just above or below the current demon.
  369. ; Note: We are checking if all values in these six blocks are Wall values.
  370. ; This code depends on the fact that Wall characters are zero and the sum
  371. ; of these six blocks will be zero if a move is possible.
  372.  
  373.         mov    al, byp Maze[bx+BytesPerRow*2]     ;Maze[x,  y+2]
  374.         add    al, byp Maze[bx+BytesPerRow*2+2] ;Maze[x+1,y+2]
  375.         add    al, byp Maze[bx+BytesPerRow*2-2] ;Maze[x-1,y+2]
  376.         je    ReturnTrue
  377.  
  378.         mov    al, byp Maze[bx-BytesPerRow*2]     ;Maze[x,  y-2]
  379.         add    al, byp Maze[bx-BytesPerRow*2+2] ;Maze[x+1,y-2]
  380.         add    al, byp Maze[bx-BytesPerRow*2-2] ;Maze[x-1,y-2]
  381.         je    ReturnTrue
  382.  
  383. ReturnFalse:    clc                ;Clear carry = false.
  384.         pop    bx
  385.         pop    ax
  386.         ret
  387.  
  388. ; If the demon is going in a north or south direction, we can start a
  389. ; new tunnel if there are six wall blocks just to the left or right
  390. ; of the current demon.
  391.  
  392. NorthSouth:    mov    al, byp Maze[bx+4]        ;Maze[x+2,y]
  393.         add    al, byp Maze[bx+BytesPerRow+4]    ;Maze[x+2,y+1]
  394.         add    al, byp Maze[bx-BytesPerRow+4]    ;Maze[x+2,y-1]
  395.         je    ReturnTrue
  396.  
  397.         mov    al, byp Maze[bx-4]        ;Maze[x-2,y]
  398.         add    al, byp Maze[bx+BytesPerRow-4]    ;Maze[x-2,y+1]
  399.         add    al, byp Maze[bx-BytesPerRow-4]    ;Maze[x-2,y-1]
  400.         jne    ReturnFalse
  401.  
  402. ReturnTrue:    stc                ;Set carry = true.
  403.         pop    bx
  404.         pop    ax
  405.         ret
  406. CanStart    endp
  407.  
  408.  
  409.  
  410.  
  411. ; CanMove-    Tests to see if the current demon (dir=cl, x=dl, y=dh) can
  412. ;        move in the specified direction.  Movement is possible if
  413. ;        the demon will not come within one square of another tunnel.
  414. ;        This function returns true (carry set) if a move is possible.
  415. ;        On entry, CH contains the direction this code should test.
  416.  
  417. CanMove        proc
  418.         push    ax
  419.         push    bx
  420.  
  421.         MazeAdrs            ;Put @Maze[x,y] into ax.
  422.         mov    bx, ax
  423.  
  424.         cmp    ch, South
  425.         jb    IsNorth
  426.         je    IsSouth
  427.         cmp    ch, East
  428.         je    IsEast
  429.  
  430. ; If the demon is moving west, check the blocks in the rectangle formed
  431. ; by Maze[x-2,y-1] to Maze[x-1,y+1] to make sure they are all wall values.
  432.  
  433.         mov    al, byp Maze[bx-BytesPerRow-4]    ;Maze[x-2, y-1]
  434.         add    al, byp Maze[bx-BytesPerRow-2]    ;Maze[x-1, y-1]
  435.         add    al, byp Maze[bx-4]        ;Maze[x-2, y]
  436.         add    al, byp Maze[bx-2]        ;Maze[x-1, y]
  437.         add    al, byp Maze[bx+BytesPerRow-4]    ;Maze[x-2, y+1]
  438.         add    al, byp Maze[bx+BytesPerRow-2]    ;Maze[x-1, y+1]
  439.         je    ReturnTrue
  440. ReturnFalse:    clc
  441.         pop    bx
  442.         pop    ax
  443.         ret
  444.  
  445.  
  446. ; If the demon is going east, check the blocks in the rectangle formed
  447. ; by Maze[x+1,y-1] to Maze[x+2,y+1] to make sure they are all wall values.
  448.  
  449. IsEast:        mov    al, byp Maze[bx-BytesPerRow+4]    ;Maze[x+2, y-1]
  450.         add    al, byp Maze[bx-BytesPerRow+2]    ;Maze[x+1, y-1]
  451.         add    al, byp Maze[bx+4]        ;Maze[x+2, y]
  452.         add    al, byp Maze[bx+2]        ;Maze[x+1, y]
  453.         add    al, byp Maze[bx+BytesPerRow+4]    ;Maze[x+2, y+1]
  454.         add    al, byp Maze[bx+BytesPerRow+2]    ;Maze[x+1, y+1]
  455.         jne    ReturnFalse
  456. ReturnTrue:    stc
  457.         pop    bx
  458.         pop    ax
  459.         ret
  460.  
  461.  
  462. ; If the demon is going north, check the blocks in the rectangle formed
  463. ; by Maze[x-1,y-2] to Maze[x+1,y-1] to make sure they are all wall values.
  464.  
  465. IsNorth:    mov    al, byp Maze[bx-BytesPerRow-2]    ;Maze[x-1, y-1]
  466.         add    al, byp Maze[bx-BytesPerRow*2-2];Maze[x-1, y-2]
  467.         add    al, byp Maze[bx-BytesPerRow]    ;Maze[x,   y-1]
  468.         add    al, byp Maze[bx-BytesPerRow*2]    ;Maze[x,   y-2]
  469.         add    al, byp Maze[bx-BytesPerRow+2]    ;Maze[x+1, y-1]
  470.         add    al, byp Maze[bx-BytesPerRow*2+2];Maze[x+1, y-2]
  471.         jne    ReturnFalse
  472.         stc
  473.         pop    bx
  474.         pop    ax
  475.         ret
  476.  
  477.  
  478.  
  479. ; If the demon is going south, check the blocks in the rectangle formed
  480. ; by Maze[x-1,y+2] to Maze[x+1,y+1] to make sure they are all wall values.
  481.  
  482. IsSouth:    mov    al, byp Maze[bx+BytesPerRow-2]    ;Maze[x-1, y+1]
  483.         add    al, byp Maze[bx+BytesPerRow*2-2];Maze[x-1, y+2]
  484.         add    al, byp Maze[bx+BytesPerRow]    ;Maze[x,   y+1]
  485.         add    al, byp Maze[bx+BytesPerRow*2]    ;Maze[x,   y+2]
  486.         add    al, byp Maze[bx+BytesPerRow+2]    ;Maze[x+1, y+1]
  487.         add    al, byp Maze[bx+BytesPerRow*2+2];Maze[x+1, y+2]
  488.         jne    ReturnFalse
  489.         stc
  490.         pop    bx
  491.         pop    ax
  492.         ret
  493.  
  494. CanMove        endp
  495.  
  496.  
  497.  
  498.  
  499. ; SetDir- Changes the current direction.  The maze digging algorithm has
  500. ; decided to change the direction of the tunnel begin dug by one
  501. ; of the demons.  This code checks to see if we CAN change the direction,
  502. ; and picks a new direction if possible.
  503. ;
  504. ; If the demon is going north or south, a direction change causes the demon
  505. ; to go east or west.  Likewise, if the demon is going east or west, a
  506. ; direction change forces it to go north or south.  If the demon cannot
  507. ; change directions (because it cannot move in the new direction for one
  508. ; reason or another), SetDir returns without doing anything.  If a direction
  509. ; change is possible, then SetDir selects a new direction.  If there is only
  510. ; one possible new direction, the demon is sent off in that direction.
  511. ; If the demon could move off in one of two different directions, SetDir
  512. ; "flips a coin" to choose one of the two new directions.
  513. ;
  514. ; This function returns the new direction in al.
  515.  
  516. SetDir        proc    near
  517.  
  518.         test    cl, 10b            ;See if north/south
  519.         je    IsNS            ; or east/west direction.
  520.  
  521. ; We're going east or west.  If we can move EITHER north or south from
  522. ; this point, randomly choose one of the directions.  If we can only
  523. ; move one way or the other, choose that direction.  If we can't go either
  524. ; way, return without changing the direction.
  525.  
  526.         mov    ch, North        ;See if we can move north
  527.         call    CanMove
  528.         jnc    NotNorth
  529.         mov    ch, South        ;See if we can move south
  530.         call    CanMove
  531.         jnc    DoNorth
  532.         call    RandNum            ;Get a random direction
  533.         and    ax, 1            ;Make it north or south.
  534.         ret
  535.  
  536. DoNorth:    mov    ax, North
  537.         ret
  538.  
  539. NotNorth:    mov    ch, South
  540.         call    CanMove
  541.         jnc    TryReverse
  542. DoSouth:    mov    ax, South
  543.         ret
  544.  
  545.  
  546.  
  547. ; If the demon is moving north or south, choose a new direction of east
  548. ; or west, if possible.
  549.  
  550. IsNS:        mov    ch, East        ;See if we can move East
  551.         call    CanMove
  552.         jnc    NotEast
  553.         mov    ch, West        ;See if we can move West
  554.         call    CanMove
  555.         jnc    DoEast
  556.         call    RandNum            ;Get a random direction
  557.         and    ax, 1b            ;Make it East or West
  558.         or    al, 10b
  559.         ret
  560.  
  561. DoEast:        mov    ax, East
  562.         ret
  563.  
  564. DoWest:        mov    ax, West
  565.         ret
  566.  
  567. NotEast:    mov    ch, West
  568.         call    CanMove
  569.         jc    DoWest
  570.  
  571. ; Gee, we can't switch to a perpendicular direction, see if we can
  572. ; turn around.
  573.  
  574. TryReverse:    mov    ch, cl
  575.         xor    ch, 1
  576.         call    CanMove
  577.         jc    ReverseDir
  578.  
  579. ; If we can't turn around (likely), then keep going in the same direction.
  580.  
  581.         mov    ah, 0
  582.         mov    al, cl            ;Stay in same direction.
  583.         ret
  584.  
  585. ; Otherwise reverse direction down here.
  586.  
  587. ReverseDir:    mov    ah, 0
  588.         mov    al, cl
  589.         xor    al, 1
  590.         ret
  591. SetDir        endp
  592.  
  593.  
  594.  
  595. ; Stuck-    This function checks to see if a demon is stuck and cannot
  596. ;        move in any direction.  It returns true if the demon is
  597. ;        stuck and needs to be killed.
  598.  
  599. Stuck        proc    near
  600.         mov    ch, North
  601.         call    CanMove
  602.         jc    NotStuck
  603.         mov    ch, South
  604.         call    CanMove
  605.         jc    NotStuck
  606.         mov    ch, East
  607.         call    CanMove
  608.         jc    NotStuck
  609.         mov    ch, West
  610.         call    CanMove
  611. NotStuck:    ret
  612. Stuck        endp
  613.  
  614.  
  615.  
  616. ; NextDemon-    Searches through the demon list to find the next available
  617. ;        active demon.  Return a pointer to this guy in es:di.
  618.  
  619. NextDemon    proc    near
  620.         push    ax
  621.  
  622. NDLoop:        inc    DemonIndex        ;Move on to next demon,
  623.         and    DemonIndex, ModDemons    ; MOD MaxDemons.
  624.         mov    al, size pcb        ;Compute index into
  625.         mul    DemonIndex        ; DemonList.
  626.         mov    di, ax            ;See if the demon at this
  627.         add    di, offset DemonList    ; offset is active.
  628.         cmp    byp [di].pcb.NextProc, 0
  629.         je    NDLoop
  630.  
  631.         mov    ax, ds
  632.         mov    es, ax
  633.         pop    ax
  634.         ret
  635. NextDemon    endp
  636.  
  637.  
  638.  
  639. ; Dig-        This is the demon process.
  640. ;        It moves the demon one position (if possible) in its current
  641. ;        direction.  After moving one position forward, there is
  642. ;        a 25% chance that this guy will change its direction; there
  643. ;        is a 25% chance this demon will spawn a child process to
  644. ;        dig off in a perpendicular direction.
  645.  
  646. Dig        proc    near
  647.  
  648. ; See if the current demon is stuck.  If the demon is stuck, then we've
  649. ; go to remove it from the demon list.  If it is not stuck, then have it
  650. ; continue digging.  If it is stuck and this is the last active demon,
  651. ; then return control to the main program.
  652.  
  653.         call    Stuck
  654.         jc    NotStuck
  655.  
  656. ; Okay, kill the current demon.
  657. ; Note: this will never kill the last demon because we have the timer
  658. ; process running.  The timer process is the one that always stops
  659. ; the program.
  660.  
  661.         dec    DemonCnt
  662.  
  663. ; Since the count is not zero, there must be more demons in the demon
  664. ; list.  Free the stack space associated with the current demon and
  665. ; then search out the next active demon and have at it.
  666.  
  667. MoreDemons:    mov    al, size pcb
  668.         mul    DemonIndex
  669.         mov    bx, ax
  670.  
  671. ; Free the stack space associated with this process.  Note this code is
  672. ; naughty.  It assumes the stack is allocated with the Standard Library
  673. ; malloc routine that always produces a base address of 8.
  674.  
  675.         mov    es, DemonList[bx].regss
  676.         mov    di, 8                ;Cheating!
  677.         free
  678.  
  679. ; Mark the demon entry for this guy as unused.
  680.  
  681.         mov    byp DemonList[bx].NextProc, 0    ;Mark as unused.
  682.  
  683.  
  684. ; Okay, locate the next active demon in the list.
  685.  
  686. FndNxtDmn:    call    NextDemon
  687.         cocall                ;Never returns
  688.  
  689.  
  690.  
  691.  
  692. ; If the demon is not stuck, then continue digging away.
  693.  
  694. NotStuck:    mov    ch, cl
  695.         call    CanMove
  696.         jnc    DontMove
  697.  
  698. ; If we can move, then adjust the demon's coordinates appropriately:
  699.  
  700.         cmp    cl, South
  701.         jb    MoveNorth
  702.         je    MoveSouth
  703.         cmp    cl, East
  704.         jne    MoveWest
  705.  
  706. ; Moving East:
  707.  
  708.         inc    dl
  709.         jmp    MoveDone
  710.  
  711. MoveWest:    dec    dl
  712.         jmp    MoveDone
  713.  
  714. MoveNorth:    dec    dh
  715.         jmp    MoveDone
  716.  
  717. MoveSouth:    inc    dh
  718.  
  719. ; Okay, store a NoWall value at this entry in the maze and output a NoWall
  720. ; character to the screen (if writing data to the screen).
  721.  
  722. MoveDone:    MazeAdrs
  723.         mov    bx, ax
  724.         mov    Maze[bx], NoWall
  725.  
  726.         ifdef    ToScreen
  727.         ScrnAdrs
  728.         mov    bx, ax
  729.         push    es
  730.         mov    ax, ScreenSeg
  731.         mov    es, ax
  732.         mov    word ptr es:[bx], NoWallChar
  733.         pop    es
  734.         endif
  735.  
  736. ; Before leaving, see if this demon shouldn't change direction.
  737.  
  738. DontMove:    call    RandNum
  739.         and    al, 11b            ;25% chance result is zero.
  740.         jne    NoChangeDir
  741.         call    SetDir
  742.         mov    cl, al
  743.  
  744. NoChangeDir:
  745.  
  746.  
  747. ; Also, see if this demon should spawn a child process
  748.  
  749.         call    RandNum
  750.         and    al, 11b            ;Give it a 25% chance.
  751.         jne    NoSpawn
  752.  
  753. ; Okay, see if it's possible to spawn a new process at this point:
  754.  
  755.         call    CanStart
  756.         jnc    NoSpawn
  757.  
  758. ; See if we've already got MaxDemons active:
  759.  
  760.         cmp    DemonCnt, MaxDemons
  761.         jae    NoSpawn
  762.  
  763.         inc    DemonCnt            ;Add another demon.
  764.  
  765.  
  766. ; Okay, create a new demon and add him to the list.
  767.  
  768.         push    dx                ;Save cur demon info.
  769.         push    cx
  770.  
  771. ; Locate a free slot for this demon
  772.  
  773.         lea    si, DemonList- size pcb
  774. FindSlot:    add    si, size pcb
  775.         cmp    byp [si].pcb.NextProc, 0
  776.         jne    FindSlot
  777.  
  778.  
  779. ; Allocate some stack space for the new demon.
  780.  
  781.         mov    cx, 256                ;256 byte stack.
  782.         malloc
  783.  
  784. ; Set up the stack pointer for this guy:
  785.  
  786.         add    di, 248                ;Point stack at end.
  787.         mov    [si].pcb.regss, es
  788.         mov    [si].pcb.regsp, di
  789.  
  790. ; Set up the execution address for this guy:
  791.  
  792.         mov    [si].pcb.regcs, cs
  793.         mov    [si].pcb.regip, offset Dig
  794.  
  795. ; Initial coordinates and direction for this guy:
  796.  
  797.         mov    [si].pcb.regdx, dx
  798.  
  799. ; Select a direction for this guy.
  800.  
  801.         pop    cx            ;Retrieve direction.
  802.         push    cx
  803.  
  804.         call    SetDir
  805.         mov    ah, 0
  806.         mov    [si].pcb.regcx, ax
  807.  
  808. ; Set up other misc junk:
  809.  
  810.         mov    [si].pcb.regds, seg dseg
  811.         sti
  812.         pushf
  813.         pop    [si].pcb.regflags
  814.         mov    byp [si].pcb.NextProc, 1    ;Mark active.
  815.  
  816.  
  817. ; Restore current process' parameters
  818.  
  819.         pop    cx            ;Restore current demon.
  820.         pop    dx
  821.  
  822. NoSpawn:
  823.  
  824. ; Okay, with all of the above done, it's time to pass control on to a new
  825. ; digger.  The following cocall passes control to the next digger in the
  826. ; DemonList.
  827.  
  828. GetNextDmn:    call    NextDemon
  829.  
  830. ; Okay, we've got a pointer to the next demon in the list (might be the
  831. ; same demon if there's only one), pass control to that demon.
  832.  
  833.         cocall
  834.         jmp    Dig
  835. Dig        endp
  836.  
  837.  
  838. ; TimerDemon-    This demon introduces a 1/18th second delay between
  839. ;        each cycle in the demon list.  This slows down the
  840. ;        maze generation so you can see the maze being built
  841. ;        (which makes the program more interesting to watch).
  842.  
  843. TimerDemon    proc    near
  844.         push    es
  845.         push    ax
  846.  
  847.         mov    ax, 40h            ;BIOS variable area
  848.         mov    es, ax
  849.         mov    ax, es:[6Ch]        ;BIOS timer location
  850. Wait4Change:    cmp    ax, es:[6Ch]        ;BIOS changes this every
  851.         je    Wait4Change        ; 1/18th second.
  852.  
  853.         cmp    DemonCnt, 1
  854.         je    QuitProgram
  855.         pop    es
  856.         pop    ax
  857.         call    NextDemon
  858.         cocall
  859.         jmp    TimerDemon
  860.  
  861. QuitProgram:    cocall    MainPCB            ;Quit the program
  862. TimerDemon    endp
  863.  
  864.  
  865.  
  866.  
  867. ; What good is a maze generator program if it cannot solve the mazes it
  868. ; creates?  SolveMaze finds the solution (if any) for this maze.  It marks
  869. ; the solution path and the paths it tried, but failed on.
  870. ;
  871. ; function solvemaze(x,y:integer):boolean
  872.  
  873. sm_X        textequ    <[bp+6]>
  874. sm_Y        textequ    <[bp+4]>
  875.  
  876. SolveMaze    proc    near
  877.         push    bp
  878.         mov    bp, sp
  879.  
  880. ; See if we've just solved the maze:
  881.  
  882.         cmp    byte ptr sm_X, EndX
  883.         jne    NotSolved
  884.         cmp    byte ptr sm_Y, EndY
  885.         jne    NotSolved
  886.         mov    ax, 1            ;Return true.
  887.         pop    bp
  888.         ret    4
  889.  
  890. ; See if moving to this spot was an illegal move.  There will be
  891. ; a NoWall value at this cell in the maze if the move is legal.
  892.  
  893. NotSolved:    mov    dl, sm_X
  894.         mov    dh, sm_Y
  895.         MazeAdrs
  896.         mov    bx, ax
  897.         cmp    Maze[bx], NoWall
  898.         je    MoveOK
  899.         mov    ax, 0            ;Return failure
  900.         pop    bp
  901.         ret    4
  902.  
  903. ; Well, it is possible to move to this point, so place an appropriate
  904. ; value on the screen and keep searching for the solution.
  905.  
  906. MoveOK:        mov    Maze[bx], Visited
  907.  
  908.         ifdef    ToScreen
  909.         push    es            ;Write a "VisitChar"
  910.         ScrnAdrs            ; character to the
  911.         mov    bx, ax            ; screen at this X,Y
  912.         mov    ax, ScreenSeg        ; position.
  913.         mov    es, ax
  914.         mov    word ptr es:[bx], VisitChar
  915.         pop    es
  916.         endif
  917.  
  918. ; Recusively call SolveMaze until we get a solution.  Just call SolveMaze
  919. ; for the four possible directions (up, down, left, right) we could go.
  920. ; Since we've left "Visited" values in the Maze, we will not accidentally
  921. ; search back through the path we've already travelled.  Furthermore, if
  922. ; we cannot go in one of the four directions, SolveMaze will catch this
  923. ; immediately upon entry (see the code at the start of this routine).
  924.  
  925.         mov    ax, sm_X        ;Try the path at location
  926.         dec    ax            ; (X-1, Y)
  927.         push    ax
  928.         push    sm_Y
  929.         call    SolveMaze
  930.         test    ax, ax            ;Solution?
  931.         jne    Solved
  932.  
  933.         push    sm_X            ;Try the path at location
  934.         mov    ax, sm_Y        ; (X, Y-1)
  935.         dec    ax
  936.         push    ax
  937.         call    SolveMaze
  938.         test    ax, ax            ;Solution?
  939.         jne    Solved
  940.  
  941.         mov    ax, sm_X        ;Try the path at location
  942.         inc    ax            ; (X+1, Y)
  943.         push    ax
  944.         push    sm_Y
  945.         call    SolveMaze
  946.         test    ax, ax            ;Solution?
  947.         jne    Solved
  948.  
  949.         push    sm_X            ;Try the path at location
  950.         mov    ax, sm_Y        ; (X, Y+1)
  951.         inc    ax
  952.         push    ax
  953.         call    SolveMaze
  954.         test    ax, ax            ;Solution?
  955.         jne    Solved
  956.         pop    bp
  957.         ret    4
  958.  
  959. Solved:
  960.         ifdef    ToScreen        ;Draw return path.
  961.         push    es
  962.         mov    dl, sm_X
  963.         mov    dh, sm_Y
  964.         ScrnAdrs
  965.         mov    bx, ax
  966.         mov    ax, ScreenSeg
  967.         mov    es, ax
  968.         mov    word ptr es:[bx], PathChar
  969.         pop    es
  970.         mov    ax, 1            ;Return true
  971.         endif
  972.  
  973.         pop    bp
  974.         ret    4
  975. SolveMaze    endp
  976.  
  977.  
  978.  
  979. ; Here's the main program that drives the whole thing:
  980.  
  981. Main        proc
  982.         mov    ax, dseg
  983.         mov    ds, ax
  984.         mov    es, ax
  985.         meminit
  986.  
  987.  
  988.         call    Init            ;Initialize maze stuff.
  989.         lesi    MainPCB            ;Initialize coroutine
  990.         coinit                ; package.
  991.  
  992. ; Create the first demon.
  993. ; Set up the stack pointer for this guy:
  994.  
  995.         mov    cx, 256
  996.         malloc
  997.         add    di, 248
  998.         mov    DemonList.regsp, di
  999.         mov    DemonList.regss, es
  1000.  
  1001. ; Set up the execution address for this guy:
  1002.  
  1003.         mov    DemonList.regcs, cs
  1004.         mov    DemonList.regip, offset Dig
  1005.  
  1006. ; Initial coordinates and direction for this guy:
  1007.  
  1008.         mov    cx, East        ;Start off going east.
  1009.         mov    dh, StartY
  1010.         mov    dl, StartX
  1011.         mov    DemonList.regcx, cx
  1012.         mov    DemonList.regdx, dx
  1013.  
  1014. ; Set up other misc junk:
  1015.  
  1016.         mov    DemonList.regds, seg dseg
  1017.         sti
  1018.         pushf
  1019.         pop    DemonList.regflags
  1020.         mov    byp DemonList.NextProc, 1    ;Demon is "active".
  1021.         inc    DemonCnt
  1022.         mov    DemonIndex, 0
  1023.  
  1024.  
  1025.  
  1026.  
  1027. ; Set up the Timer demon:
  1028.  
  1029.         mov    DemonList.regsp+(size pcb), offset EndTimerStk
  1030.         mov    DemonList.regss+(size pcb), ss
  1031.  
  1032. ; Set up the execution address for this guy:
  1033.  
  1034.         mov    DemonList.regcs+(size pcb), cs
  1035.         mov    DemonList.regip+(size pcb), offset TimerDemon
  1036.  
  1037. ; Set up other misc junk:
  1038.  
  1039.         mov    DemonList.regds+(size pcb), seg dseg
  1040.         sti
  1041.         pushf
  1042.         pop    DemonList.regflags+(size pcb)
  1043.         mov    byp DemonList.NextProc+(size pcb), 1
  1044.         inc    DemonCnt
  1045.  
  1046. ; Start the ball rolling.
  1047.  
  1048.         mov    ax, ds
  1049.         mov    es, ax
  1050.         lea    di, DemonList
  1051.         cocall
  1052.  
  1053. ; Wait for the user to press a key before solving the maze:
  1054.  
  1055.         getc
  1056.  
  1057.         mov    ax, StartX
  1058.         push    ax
  1059.         mov    ax, StartY
  1060.         push    ax
  1061.         call    SolveMaze
  1062.  
  1063. ; Wait for another keystroke before quitting:
  1064.  
  1065.         getc
  1066.  
  1067.         mov    ax, 3        ;Clear screen and reset video mode.
  1068.         int    10h
  1069.  
  1070. Quit:        ExitPgm            ;DOS macro to quit program.
  1071. Main        endp
  1072.  
  1073. cseg        ends
  1074.  
  1075. sseg        segment    para stack 'stack'
  1076.  
  1077. ; Stack for the timer demon we create (we'll allocate the other
  1078. ; stacks dynamically).
  1079.  
  1080. TimerStk    byte    256 dup (?)
  1081. EndTimerStk    word    ?
  1082.  
  1083.  
  1084. ; Main program's stack:
  1085.  
  1086. stk        byte    512 dup (?)
  1087. sseg        ends
  1088.  
  1089. zzzzzzseg    segment    para public 'zzzzzz'
  1090. LastBytes    db    16 dup (?)
  1091. zzzzzzseg    ends
  1092.         end    Main
  1093.